//
//  236_二叉树的最近公共祖先.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/13.
/*
 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
 */

import UIKit

class GetParentNode: NSObject {
    func lowestCommonAncestor(_ root: TreeNode<Int>?, _ p: TreeNode<Int>?, _ q: TreeNode<Int>?) -> TreeNode<Int>? {
        if root == nil || root === p || root === q {
            return root
        }
        let left = lowestCommonAncestor(root?.left, p, q)
        let right = lowestCommonAncestor(root?.right, p, q)
        if left == nil && right == nil {
            return nil
        }
        if left != nil && right != nil {
            return root
        }
        if left != nil && right == nil {
            return left
        }
        if left == nil && right != nil {
            return right
        }
        return root
    }
    
    func getCommonNode(_ root: TreeNode<Int>?, p: TreeNode<Int>, q: TreeNode<Int>) -> TreeNode<Int>? {
        
        if root == nil || root === p || root === q {
            return root
        }
        
        let left = getCommonNode(root?.left, p: p, q: q)
        let right = getCommonNode(root?.right, p: p, q: q)
        if left == nil && right == nil {
            return nil
        }
        if left != nil && right != nil {
            return root
        }
        if left != nil && right == nil {
            return left
        }
        
        if left == nil && right != nil {
            return right
        }
        return root
    }
}
